package leetcodecompetition.D347;

import java.util.Arrays;

/**
 * @Author: Siantar
 * @Date: 2023-05-28-11:44
 * @Description: 1.0
 */
public class T6456 {
    int[][] res;
    int[][] mat;
    int[][] dict = new int[][]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    int m, n;

    public int maxIncreasingCells(int[][] mat) {
        m = mat.length;
        n = mat[0].length;
        res = new int[m][n];
        this.mat = mat;
        for (int i = 0; i < m; i++) {
            Arrays.fill(res[i], -1);
        }
        int max = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(max, help(i, j));
                System.out.println(i+" "+j+" "+max);
            }
        }
        return max;
    }

    public int help(int a, int b) {
        if (res[a][b] != -1) return res[a][b];
        int max = 1;
        for (int i = 0; i <m ; i++) {
            if(i==a)continue;
            if (mat[i][b] > mat[a][b]) {
                max = Math.max(max, help(i, b) + 1);
            }
        }
        for (int i = 0; i <n ; i++) {
            if(i==b)continue;
            if (mat[a][i] > mat[a][b]) {
                max = Math.max(max, help(a, i) + 1);
            }
        }
        res[a][b] = max;
        return max;
    }
}
